English+GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Spannbaum</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Spannbaum</h1>

</header>

</div>

Ein Spannbaum (auch aufspannender Baum oder Gerüst genannt; englisch spanning tree, manchmal <a href="Falscher_Freund" title="Falscher Freund">fälschlich</a> als „spannender Baum“ übersetzt) ist in der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> ein <a href="Teilgraph" title="Teilgraph">Teilgraph</a> eines <a href="Ungerichteter_Graph" class="mw-redirect" title="Ungerichteter Graph">ungerichteten Graphen</a>, der ein <a href="Baum_(Graphentheorie)" title="Baum (Graphentheorie)">Baum</a> ist und alle Knoten dieses Graphen enthält.<a href="#cite_note-1">[1]</a> Spannbäume existieren nur in <a href="Zusammenhang_von_Graphen" class="mw-redirect" title="Zusammenhang von Graphen">zusammenhängenden</a> Graphen.

In einem <a href="Vollst%C3%A4ndiger_Graph" title="Vollständiger Graph">vollständigen Graphen</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ea2b988ea630d2c5571afe47efa3d3b251708acb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.192ex; height:2.509ex;" alt="{\displaystyle K_{n}}" loading="lazy"> findet man nach der <a href="Cayley-Formel" title="Cayley-Formel">Cayley-Formel</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{n-2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{n-2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65a6e7866523a163c773c59df1fc7793ef534c56.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.714ex; height:2.676ex;" alt="{\displaystyle n^{n-2}}" loading="lazy"> verschiedene Spannbäume. Im nebenstehenden Beispiel des <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{4}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{4}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fe633da926900748cc19ee1ffec1853834a6c061.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.027ex; height:2.509ex;" alt="{\displaystyle K_{4}}" loading="lazy"> sind es <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 4^{4-2}=16}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 4^{4-2}=16}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7fc84e2779a4a1d949d127be335d85c935c15e82.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.741ex; height:2.676ex;" alt="{\displaystyle 4^{4-2}=16}" loading="lazy"> Stück.

<div class="mw-heading mw-heading2"><h2 id="Unterarten">Unterarten</h2></div>

Ein Teilgraph, der in einem Graphen für jede <a href="Zusammenhang_von_Graphen" class="mw-redirect" title="Zusammenhang von Graphen">Komponente</a> einen Spannbaum ergibt, wird Gerüst, Spannwald oder aufspannender <a href="Wald_(Graphentheorie)" title="Wald (Graphentheorie)">Wald</a> genannt. Dabei muss der Graph nicht notwendigerweise zusammenhängend sein. In zusammenhängenden Graphen sind Gerüst und Spannbaum identische Begriffe, während Spannbäume für unzusammenhängende Graphen per Definition nicht existieren.

In <a href="Kantengewichteter_Graph" title="Kantengewichteter Graph">kantengewichteten</a> Graphen lässt sich als Gewicht eines Graphen die Summe seiner Kantengewichte definieren. Ein Spannbaum bzw. ein Gerüst heißt minimal, wenn kein anderer Spannbaum bzw. kein anderes Gerüst in demselben Graphen mit geringerem Gewicht existiert. Häufig wird minimaler Spannbaum auch mit MST (Abkürzung des englischen Begriffs Minimum Spanning Tree) oder MCST (Minimum Cost Spanning Tree – ein Spannbaum mit minimalen Kosten) abgekürzt. Statt minimales Gerüst sagt man auch Minimalgerüst oder Gerüst kleinsten Wertes. Ist die Kantengewichtungsfunktion injektiv, so ist der minimale Spannbaum eindeutig.

Ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">-Spanner eines Graphen ist ein aufspannender Teilgraph, in dem die <a href="Abstand_(Graphentheorie)" class="mw-redirect" title="Abstand (Graphentheorie)">Distanz</a> jedes Knotenpaares höchstens dem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

Bei einem gradbeschränkten Spannbaum dürfen nicht beliebig viele Kanten an einem Knoten zusammenlaufen.

<div class="mw-heading mw-heading2"><h2 id="Algorithmen">Algorithmen</h2></div>

Ein nicht minimaler Spannbaum kann in einem <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graphen</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy"> mit Knotenmenge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> und Kantenmenge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> mittels <a href="Breitensuche" title="Breitensuche">Breiten-</a> oder <a href="Tiefensuche" title="Tiefensuche">Tiefensuche</a> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}{\bigl (}\left|V\right|+\left|E\right|{\bigr )}}">

</mrow>

</mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}{\bigl (}\left|V\right|+\left|E\right|{\bigr )}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c4dfeeccd6c6f70b91ed8c2fe320faa7e294eda.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.745ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}{\bigl (}\left|V\right|+\left|E\right|{\bigr )}}" loading="lazy"> gefunden werden.

Zur effizienten Berechnung minimaler Spannbäume existiert eine Vielzahl von sequentiellen Algorithmen, zum Beispiel der <a href="Algorithmus_von_Prim" title="Algorithmus von Prim">Algorithmus von Prim</a>, der <a href="Algorithmus_von_Kruskal" title="Algorithmus von Kruskal">Algorithmus von Kruskal</a> und der <a href="Algorithmus_von_Bor%C5%AFvka" title="Algorithmus von Borůvka">Algorithmus von Borůvka</a>. Alle drei genannten Algorithmen vergrößern iterativ eine Teilmenge der Kanten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

Neben den oben genannten Algorithmen gibt es viele weitere Veröffentlichungen zur parallelen Berechnung minimaler Spannbäume. Mit einer linearen Anzahl an Prozessoren ist es möglich, das Problem in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"> Zeit zu lösen<a href="#cite_note-2">[2]</a><a href="#cite_note-3">[3]</a>. Bader und Cong präsentieren einen Algorithmus, der minimale Spannbäume fünffach schneller auf acht Prozessoren berechnet als ein optimierter sequentieller Algorithmus<a href="#cite_note-4">[4]</a>.

Weitere spezialisierte Algorithmen wurden für minimale Spannbäume im <a href="External_Memory_Minimaler_Spannbaum" title="External Memory Minimaler Spannbaum">External-Memory-Modell</a> entwickelt.<a href="#cite_note-5">[5]</a> Laut den Autoren arbeitet dieser Algorithmus nur 2–5 mal langsamer als ein Algorithmus, der nur auf dem Hauptspeicher arbeitet.

Ein Spannbaum eines <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graphen</a> kann in linearer Zeit entweder durch <a href="Tiefensuche" title="Tiefensuche">Tiefensuche</a> oder durch <a href="Breitensuche" title="Breitensuche">Breitensuche</a> gefunden werden. Beide <a href="Algorithmus" title="Algorithmus">Algorithmen</a> untersuchen den gegebenen Graphen ausgehend von einem beliebigen <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a>, indem sie die <a href="Nachbar_(Graphentheorie)" class="mw-redirect" title="Nachbar (Graphentheorie)">Nachbarn</a> der von ihnen gefundenen Knoten durchlaufen und jeden nicht gefundenen Nachbarn zu einer <a href="Datenstruktur" title="Datenstruktur">Datenstruktur</a> hinzufügen, die später untersucht werden soll. Sie unterscheiden sich darin, ob es sich bei dieser Datenstruktur um einen <a href="Stapelspeicher" title="Stapelspeicher">Stapelspeicher</a> (bei der Tiefensuche) oder eine <a href="Warteschlange_(Datenstruktur)" title="Warteschlange (Datenstruktur)">Warteschlange</a> (bei der Breitensuche) handelt. In beiden Fällen kann ein Spannbaum gebildet werden, indem jeder andere Knoten als der Wurzelknoten mit dem Knoten verbunden wird, von dem aus er gefunden wurde. Dieser Baum ist als Tiefensuchbaum oder Breitensuchbaum gemäß dem zur Erstellung verwendeten <a href="Graphsuchalgorithmus" class="mw-redirect" title="Graphsuchalgorithmus">Graphsuchsalgorithmus</a> bekannt.<a href="#cite_note-6">[6]</a>

Spannbäume sind wichtig für <a href="Parallelrechner" title="Parallelrechner">Parallelrechner</a> und <a href="Verteiltes_System" title="Verteiltes System">verteilte Systeme</a>, um die Kommunikation zwischen einer Reihe von Prozessoren aufrechtzuerhalten. Siehe zum Beispiel das <a href="Spanning_Tree_Protocol" title="Spanning Tree Protocol">Spanning Tree Protocol</a> oder das Shout Protocol für verteilte Systeme. Die <a href="Tiefensuche" title="Tiefensuche">Tiefensuche</a> und <a href="Breitensuche" title="Breitensuche">Breitensuche</a> zum Erstellen von Spannbäumen auf sequentiellen <a href="Computer" title="Computer">Computern</a> sind jedoch für Parallelrechner und verteilte Systeme nicht gut geeignet.<a href="#cite_note-7">[7]</a> Stattdessen haben Forscher mehrere spezialisiertere Algorithmen entwickelt, um Spannbäume in diesen Berechnungsmodellen zu finden.<a href="#cite_note-8">[8]</a>

Optimale Spannbäume wurden auch für endliche Punktmengen in einem geometrischen <a href="Raum_(Mathematik)" title="Raum (Mathematik)">Raum</a> wie der <a href="Euklidischer_Raum" title="Euklidischer Raum">euklidischen</a> <a href="Ebene_(Mathematik)" title="Ebene (Mathematik)">Ebene</a> untersucht. Für eine solche Eingabe ist ein Spannbaum wieder ein <a href="Baum_(Graphentheorie)" title="Baum (Graphentheorie)">Baum</a>, dessen <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> die angegebenen <a href="Punkt_(Geometrie)" title="Punkt (Geometrie)">Punkte</a> sind. Die Qualität des Baums wird auf die gleiche Weise wie in einem Graphen gemessen, wobei der <a href="Euklidischer_Abstand" title="Euklidischer Abstand">euklidische Abstand</a> zwischen Punktpaaren als Gewicht für jede <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kante</a> verwendet wird. So entspricht beispielsweise ein euklidischer minimaler Spannbaum einem minimalen Spannbaum in einem vollständigen Graphen mit euklidischen Kantengewichten. Es ist jedoch nicht erforderlich, diesen Graphen zu erstellen, um das <a href="Optimierungsproblem" title="Optimierungsproblem">Optimierungsproblem</a> zu lösen. Das Problem des euklidischen minimalen Spannbaums kann beispielsweise effizienter mit einer <a href="Laufzeit_(Informatik)" title="Laufzeit (Informatik)">Laufzeit</a> in der Größenordnung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\cdot \log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\cdot \log n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/837218b6d28ce003c0f81f7af156da3ede782fe1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.41ex; height:2.843ex;" alt="{\displaystyle O(n\cdot \log n)}" loading="lazy"> gelöst werden, indem die <a href="Delaunay-Triangulierung" title="Delaunay-Triangulierung">Delaunay-Triangulierung</a> erstellt und anschließend ein <a href="Algorithmus" title="Algorithmus">Algorithmus</a> mit linearer Laufzeit für den minimalen Spannbaum eines <a href="Planarer_Graph" title="Planarer Graph">planaren Graphen</a> auf die resultierende Triangulierung angewendet wird.<a href="#cite_note-9">[9]</a>

<div class="mw-heading mw-heading2"><h2 id="Anwendungen">Anwendungen</h2></div>

Die Berechnung minimaler Spannbäume findet direkte Anwendung in der Praxis, beispielsweise für die Erstellung von kostengünstigen zusammenhängenden Netzwerken, wie beispielsweise Telefonnetze oder elektrische Netze. Ein Telefon- oder Netzbetreiber möchte z. B. Städte verbinden und dabei möglichst wenig Geld für z. B. Kabel ausgeben. Auch bei <a href="Rechnernetz" title="Rechnernetz">Rechnernetzen</a> mit redundanten Pfaden werden zur Vermeidung von durch einen Broadcast entstandenen Paketverdopplungen Spannbäume genutzt (siehe <a href="Spanning_Tree_Protocol" title="Spanning Tree Protocol">Spanning Tree Protocol</a>).

In der Graphentheorie selbst sind MST-Algorithmen häufig Grundlage komplexerer Algorithmen für schwierigere Probleme. Die Berechnung minimaler Spannbäume ist zum Beispiel Bestandteil von <a href="Approximationsalgorithmus" title="Approximationsalgorithmus">Approximationsalgorithmen</a> für das <a href="Problem_des_Handlungsreisenden" title="Problem des Handlungsreisenden">Problem des Handlungsreisenden</a>, oft auch in der englischen Bezeichnung travelling salesman problem (TSP) genannt (siehe <a href="MST-Heuristik" title="MST-Heuristik">MST-Heuristik</a>), oder für das <a href="Steinerbaumproblem" title="Steinerbaumproblem">Steinerbaumproblem</a>. Letzteres ist auch eine Verallgemeinerung des Problems, einen minimalen Spannbaum zu finden.

Des Weiteren spielen Spannbäume bei der algorithmischen Erzeugung von <a href="Labyrinth" title="Labyrinth">Labyrinthen</a> eine Rolle. Ein Knoten im Spannbaum entspricht dabei einem Feld, während eine Kante einen möglichen Übergang zu einem Nachbarfeld darstellt. Eine fehlende Kante beschreibt folglich eine Wand. Da Spannbäume wie alle Bäume zyklenfrei sind, besitzt ein mittels Spannbäumen erzeugtes Labyrinth stets nur einen einzigen Lösungsweg.

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Jaroslav Nesetril, Eva Milková, Helena Nesetrilová: Otakar Borůvka on minimum spanning tree problem: Translation of both the 1926 papers, comments, history, Discrete Mathematics, 233 (2001), Seiten 3–36.</li>

<li><a href="Bernard_Chazelle" title="Bernard Chazelle">Bernard Chazelle</a>: <a rel="nofollow" class="external text" href="http://www.cs.princeton.edu/~chazelle/pubs/mst.pdf">A minimum spanning tree algorithm with inverse-Ackermann type complexity</a> (PDF; 321 kB). Journal ACM 47 (2000), Seiten 1028–1047.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"></div><a href="https://de.wikiversity.org/wiki/Kurs:Diskrete_Mathematik_(Osnabr%C3%BCck_2020)/Vorlesung_18" class="extiw external" title="v:Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 18">Wikiversity: Eine Vorlesung über Spannbäume im Rahmen eines Kurses zur diskreten Mathematik</a> – Kursmaterialien</div>

<ul><li>Katharina Langkau, Martin Skutella: <a rel="nofollow" class="external text" href="http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php">Minimal aufspannende Bäume</a>, Algorithmus der Woche, 25. Juli 2006. Fakultätentag Informatik.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Anmerkungen">Anmerkungen</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> Ein vergleichbares Problem auf <a href="Gerichteter_Graph" title="Gerichteter Graph">gerichteten Graphen</a> ist das Finden eines Teilgraphen, der ein <a href="Gewurzelter_Baum" title="Gewurzelter Baum">gewurzelter Baum</a> ist.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> Ka Wong Chong, Yijie Han, Tak Wah Lam: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Concurrent threads and optimal parallel minimum spanning trees algorithm</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Journal of the Association for Computing Machinery</cite>. 48. Jahrgang, Nr. 2, 2001, S. 297–323, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145/375827.375847">10.1145/375827.375847</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Spannbaum&rft.atitle=Concurrent+threads+and+optimal+parallel+minimum+spanning+trees+algorithm&rft.au=Ka+Wong%26%2332%3BChong%2C%26%2332%3BYijie%26%2332%3BHan%2C%26%2332%3BTak+Wah%26%2332%3BLam&rft.date=2001&rft.doi=10.1145%2F375827.375847&rft.genre=journal&rft.issue=2&rft.jtitle=Journal+of+the+Association+for+Computing+Machinery&rft.pages=297-323&rft.volume=48.+Jahrgang" style="display:none">

</li>

<li id="cite_note-3"><a href="#cite_ref-3">↑</a> Seth Pettie, Vijaya Ramachandran: <cite class="lang" lang="en" dir="auto" style="font-style:italic">A randomized time-work optimal parallel algorithm for finding a minimum spanning forest</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">SIAM Journal on Computing</cite>. 31. Jahrgang, Nr. 6, 2002, S. 1879–1895, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137/S0097539700371065">10.1137/S0097539700371065</a> (englisch, <a rel="nofollow" class="external text" href="http://www.eecs.umich.edu/~pettie/papers/sicomp-randmst.pdf">umich.edu</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Spannbaum&rft.atitle=A+randomized+time-work+optimal+parallel+algorithm+for+finding+a+minimum+spanning+forest&rft.au=Seth%26%2332%3BPettie%2C%26%2332%3BVijaya%26%2332%3BRamachandran&rft.date=2002&rft.doi=10.1137%2FS0097539700371065&rft.genre=journal&rft.issue=6&rft.jtitle=SIAM+Journal+on+Computing&rft.pages=1879-1895&rft.volume=31.+Jahrgang" style="display:none">

</li>

<li id="cite_note-4"><a href="#cite_ref-4">↑</a> David A. Bader, Guojing Cong: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Journal of Parallel and Distributed Computing</cite>. 66. Jahrgang, Nr. 11, 2006, S. 1366–1378, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016/j.jpdc.2006.06.001">10.1016/j.jpdc.2006.06.001</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Spannbaum&rft.atitle=Fast+shared-memory+algorithms+for+computing+the+minimum+spanning+forest+of+sparse+graphs&rft.au=David+A.%26%2332%3BBader%2C%26%2332%3BGuojing%26%2332%3BCong&rft.date=2006&rft.doi=10.1016%2Fj.jpdc.2006.06.001&rft.genre=journal&rft.issue=11&rft.jtitle=Journal+of+Parallel+and+Distributed+Computing&rft.pages=1366-1378&rft.volume=66.+Jahrgang" style="display:none">

</li>

<li id="cite_note-5"><a href="#cite_ref-5">↑</a> Roman Dementiev, Peter Sanders, Dominik Schultes, Jop Sibeyn: <cite style="font-style:italic">Engineering an External Memory Minimum Spanning Tree Algorithm</cite>. In: <cite style="font-style:italic">Exploring New Frontiers of Theoretical Informatics – IFIP 18th World Computer Congress TC1 3rd International Conference on Theoretical Computer Science (TCS2004) 22–27 August 2004 Toulouse, France</cite> (= <cite style="font-style:italic">IFIP International Federation for Information Processing</cite>. Band 155). Springer, 2004, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007/1-4020-8141-3_17">10.1007/1-4020-8141-3_17</a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Spannbaum&rft.atitle=Engineering+an+External+Memory+Minimum+Spanning+Tree+Algorithm&rft.au=Roman+Dementiev%2C+Peter+Sanders%2C+Dominik+Schultes%2C+...&rft.btitle=Exploring+New+Frontiers+of+Theoretical+Informatics+-+IFIP+18th+World+Computer+Congress+TC1+3rd+International+Conference+on+Theoretical+Computer+Science+%28TCS2004%29+22-27+August+2004+Toulouse%2C+France&rft.date=2004&rft.doi=10.1007%2F1-4020-8141-3_17&rft.genre=book&rft.pub=Springer&rft.series=IFIP+International+Federation+for+Information+Processing" style="display:none">

</li>

<li id="cite_note-6"><a href="#cite_ref-6">↑</a> Dexter Kozen: <cite style="font-style:italic">The Design and Analysis of Algorithms</cite>. Monographs in Computer Science, 1992, ISBN 978-0-387-97687-7, S. 19.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Spannbaum&rft.au=Dexter+Kozen&rft.btitle=The+Design+and+Analysis+of+Algorithms&rft.date=1992&rft.genre=book&rft.isbn=9780387976877&rft.pages=19&rft.pub=Monographs+in+Computer+Science" style="display:none">

</li>

<li id="cite_note-7"><a href="#cite_ref-7">↑</a> John H. Reif: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Depth-first search is inherently sequential</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Information Processing Letters</cite>. 20. Jahrgang, Nr. 5, 1985, S. 229–234, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016/0020-0190%2885%2990024-9">10.1016/0020-0190(85)90024-9</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Spannbaum&rft.atitle=Depth-first+search+is+inherently+sequential&rft.au=John+H.%26%2332%3BReif&rft.date=1985&rft.doi=10.1016%2F0020-0190%2885%2990024-9&rft.genre=journal&rft.issue=5&rft.jtitle=Information+Processing+Letters&rft.pages=229-234&rft.volume=20.+Jahrgang" style="display:none"> .

</li>

<li id="cite_note-8"><a href="#cite_ref-8">↑</a> R. G. Gallager, P. A. Humblet, P. M. Spira: <cite class="lang" lang="en" dir="auto" style="font-style:italic">A distributed algorithm for minimum-weight spanning trees</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">ACM Transactions on Programming Languages and Systems</cite>. 5. Jahrgang, Nr. 1, 1983, S. 66–77, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145/357195.357200">10.1145/357195.357200</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Spannbaum&rft.atitle=A+distributed+algorithm+for+minimum-weight+spanning+trees&rft.au=R.+G.%26%2332%3BGallager%2C%26%2332%3BP.+A.%26%2332%3BHumblet%2C%26%2332%3BP.+M.%26%2332%3BSpira&rft.date=1983&rft.doi=10.1145%2F357195.357200&rft.genre=journal&rft.issue=1&rft.jtitle=ACM+Transactions+on+Programming+Languages+and+Systems&rft.pages=66-77&rft.volume=5.+Jahrgang" style="display:none"> ; Hillel Gazit: <cite class="lang" lang="en" dir="auto" style="font-style:italic">An optimal randomized parallel algorithm for finding connected components in a graph</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">SIAM Journal on Computing</cite>. 20. Jahrgang, Nr. 6, 1991, S. 1046–1067, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137/0220066">10.1137/0220066</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Spannbaum&rft.atitle=An+optimal+randomized+parallel+algorithm+for+finding+connected+components+in+a+graph&rft.au=Hillel%26%2332%3BGazit&rft.date=1991&rft.doi=10.1137%2F0220066&rft.genre=journal&rft.issue=6&rft.jtitle=SIAM+Journal+on+Computing&rft.pages=1046-1067&rft.volume=20.+Jahrgang" style="display:none"> ; David A. Bader, Guojing Cong: <cite class="lang" lang="en" dir="auto" style="font-style:italic">A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Journal of Parallel and Distributed Computing</cite>. 65. Jahrgang, Nr. 9, 2005, S. 994–1006, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016/j.jpdc.2005.03.011">10.1016/j.jpdc.2005.03.011</a> (englisch, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20150923201604/http://www.cc.gatech.edu/fac/bader/papers/SpanningTree-JPDC2005.pdf">cc.gatech.edu</a> (<a href="Webarchivierung#Begrifflichkeiten" title="Webarchivierung">Memento</a> des <style data-mw-deduplicate="TemplateStyles:r250917974">

/* start https://de.wikipedia.org/ */

.mw-parser-output .dewiki-iconexternal>a{background-position:center right!important;background-repeat:no-repeat!important}body.skin-minerva .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/OOjs_UI_icon_external-link-ltr-progressive.svg")!important;background-size:10px!important;padding-right:13px!important}body.skin-timeless .mw-parser-output .dewiki-iconexternal>a,body.skin-monobook .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/MediaWiki_external_link_icon.svg")!important;padding-right:13px!important}body.skin-vector .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/Link.ernal-small-ltr-progressive.svg")!important;background-size:0.857em!important;padding-right:1em!important}

/* end https://de.wikipedia.org/ */

</style><a class="external text" href="https://redirecter.toolforge.org/?url=http%3A%2F%2Fwww.cc.gatech.edu%2Ffac%2Fbader%2Fpapers%2FSpanningTree-JPDC2005.pdf">Originals</a> vom 23. September 2015 im <a href="Internet_Archive" title="Internet Archive">Internet Archive</a>) [abgerufen am 13. April 2020]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Spannbaum&rft.atitle=A+fast%2C+parallel+spanning+tree+algorithm+for+symmetric+multiprocessors+%28SMPs%29&rft.au=David+A.%26%2332%3BBader%2C%26%2332%3BGuojing%26%2332%3BCong&rft.date=2005&rft.doi=10.1016%2Fj.jpdc.2005.03.011&rft.genre=journal&rft.issue=9&rft.jtitle=Journal+of+Parallel+and+Distributed+Computing&rft.pages=994-1006&rft.volume=65.+Jahrgang" style="display:none"> .

</li>

<li id="cite_note-9"><a href="#cite_ref-9">↑</a> <a href="David_Eppstein" title="David Eppstein">David Eppstein</a>: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Spanning trees and spanners</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Handbook of Computational Geometry</cite>. Elsevier, 1999, S. 425–461 (englisch, <a rel="nofollow" class="external text" href="http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf">uci.edu</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Spannbaum&rft.atitle=Spanning+trees+and+spanners&rft.au=David%26%2332%3BEppstein&rft.btitle=Handbook+of+Computational+Geometry&rft.date=1999&rft.genre=book&rft.pages=425-461&rft.pub=Elsevier" style="display:none">

</li>

</ol>

<div>

Normdaten (Sachbegriff): <a href="Gemeinsame_Normdatei" title="Gemeinsame Normdatei">GND</a>: <a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4761178-9">4761178-9</a> </div>

</div></div></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-07-19" href="https://de.wikipedia.org/wiki/?title=Spannbaum&oldid=258057046">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>